package leetcode.tree;

/**
 * @author wangmaolin1
 * @date 2023/11/12 21:26
 */
public class _236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return  find(root,p.val,q.val);
    }

    private TreeNode find(TreeNode root, int p, int q) {
        if (root == null){
            return null;
        }
        // 题目确认一定存在，所以在前序位置只要当前节点是，则一定是最近公共祖先
        if (root.val == p || root.val == q){
            return root;
        }
        TreeNode left = find(root.left,p,q);
        TreeNode right = find(root.right,p,q);
        // 在后序位置，左右都找到时，当前节点为祖先
        if (left!=null && right!=null){
            return root;
        }
        return left!=null?left:right;
    }
}
